package com.eistert.java.datastructure._02_Stack;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @Description: 20. Valid Parentheses
 * @Author: ai
 * @create: 2023-04-04 15:45
 */
public class _20_ValidParentheses {

    class Solution01 {
        public boolean isValid(String s) {
            int n = s.length();
            if (n % 2 == 1) {
                return false;
            }

            Map<Character, Character> pairs = new HashMap<Character, Character>() {{
                put(')', '(');
                put(']', '[');
                put('}', '{');
            }};
            Deque<Character> stack = new LinkedList<Character>();
            for (int i = 0; i < n; i++) {
                char ch = s.charAt(i);
                if (pairs.containsKey(ch)) {
                    if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                        return false;
                    }
                    stack.pop();
                } else {
                    stack.push(ch);
                }
            }
            return stack.isEmpty();
        }
    }


    static class Solution02 {

        public boolean isValid(String s) {

            _02_Stack<Character> a02Stack = new _02_Array02Stack<>();
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(' || c == '[' || c == '{')
                    a02Stack.push(c);
                else {
                    if (a02Stack.isEmpty())
                        return false;

                    char topChar = a02Stack.pop();
                    if (c == ')' && topChar != '(')
                        return false;
                    if (c == ']' && topChar != '[')
                        return false;
                    if (c == '}' && topChar != '{')
                        return false;
                }
            }
            return a02Stack.isEmpty();
        }


    }

    public static void main(String[] args) {

        System.out.println((new Solution02()).isValid("()[]{}"));
        System.out.println((new Solution02()).isValid("([)]"));
    }


}
